#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2020年08月22日
版    本：v1.0.0
描    述：
Copyright (C) 2020 All rights reserved.
'''


class Solution:
    """
    @param source : A string
    @param target: A string
    @return: A string denote the minimum window, return "" if there is no such a string
    """
    def minWindow(self, source, target):
        # write your code here
        count_s = dict()
        count_t = dict()

        for ch in target:
            value = count_t.get(ch, 0)
            count_t[ch] = value + 1
        
        left = 0
        right = 0
        valid = 0
        start = -1
        minlen = len(source)
        
        for right in range(len(source)):
            ch = source[right]
            if ch in target:
                value = count_s.get(ch, 0)
                count_s[ch] = value + 1
                if count_s[ch] == count_t[ch]:
                    valid += 1
            
            # 判断窗口是否需要收缩
            while valid == len(count_t):
                if right - left < minlen:
                    minlen = right - left
                    start = left

                ch = source[left]
                if ch in target:
                    count_s[ch] -= 1
                    if count_s[ch] < count_t[ch]:
                        valid -= 1
                left += 1

        return "" if start == -1 else source[start: start + minlen + 1]


if __name__ == "__main__":
    A = Solution()
    print A.minWindow("adobecodebanc", "abc")